package com.company.demo4;

import com.company.demo2.MyQueue;

import java.util.Arrays;

public class RadixQueueSort {

    public static void main(String[] args) {
        int[] arr = new int[]{23,6,189,45,9,278,56,1,798,34,65,562,5};
        redixSort(arr);
        System.out.println(Arrays.toString(arr));
    }

    public static void redixSort(int[] arr){
        //存数组中最大数
        int max=0;
        for (int i=0;i<arr.length;i++){
            if (arr[i]>max){
                max=arr[i];
            }
        }
        //计算最大数字是几位数
        int maxLength = (max+"").length();
        //用于临时存储数据的队列的数组
        MyQueue[] temp = new MyQueue[10];
        //为队列数组赋值
        for(int i=0;i<temp.length;i++){
            temp[i]=new MyQueue();
        }
        //用于记录在temp中相应的数组中存放的数量
        int[] counts = new int[10];
        //根据最大长度的数决定比较的次数
        for(int i=0,n=1;i<maxLength;i++,n*=10){
            //把每一个数字分别计算余数
            for (int j=0;j<arr.length;j++){
                //计算余数
                int ys = arr[j]/n%10;
                //把当前便利的数据放入指定的队列中
                temp[ys].add(arr[j]);
                //记录数量
                counts[ys]++;
            }
            //记录取得元素需要放的位置
            int index=0;
            //把所有队列中的数字取出来
            for (int k=0;k<temp.length;k++){
                //当前便利的队列不为空
                    //循环取出元素
                    while(!temp[k].isEmpty()){
                        //取出元素
                        arr[index] = temp[k].poll();

                    }
                    //记录下一个位置
                    index++;
                    //把数量制为0
                    counts[k]=0;
            }
        }
    }

}
